Method: simulateMove(IKopplung, State, Move)

1: package de.fhdw.gaming.ipspiel23.gst.strategies.impl;
2:
3: import java.util.Collection;
4: import java.util.Optional;
5:
6: import de.fhdw.gaming.core.domain.GameException;
7: import de.fhdw.gaming.core.domain.Move;
8: import de.fhdw.gaming.core.domain.Player;
9: import de.fhdw.gaming.core.domain.State;
10: import de.fhdw.gaming.ipspiel23.gst.domain.IKopplung;
11: import de.fhdw.gaming.ipspiel23.gst.strategies.domain.IGstKopplungsMiniMaxStrategy;
12:
13: /**
14: * An implementation of the IGstKopplungsMiniMaxStrategy interface using the
15: * NegaMax algorithm with alpha beta pruning and Time based Iterative Deepening.
16: *
17: * @param <P> The type of player in the game.
18: * @param <S> The type of state in the game.
19: * @author borkowitz
20: */
21: public class GstKopplungNegaMax<P extends Player<P>, S extends State<P, S>>
22: implements IGstKopplungsMiniMaxStrategy<P, S> {
23:
24: /**
25: * Calculates the best move for the current player of a Game in a given Game state using the NegaMax algorithm.
26: * Too complex, but not easily simplifyable. Warning suppressed.
27: *
28: * @param kopplung The game object representing the specific game being played.
29: * @param state The current state of the game.
30: * @param maximumComputationTime The maximum computation time allowed for calculating the move.
31: * @return An optional containing the calculated best move, or empty if no move is available.
32: */
33: @SuppressWarnings({ "checkstyle:CyclomaticComplexity", "PMD.CyclomaticComplexity", "PMD.CognitiveComplexity",
34: "unused" })
35: @Override
36: public Optional<Move<P, S>> calculateBestMove(final IKopplung<P, S> kopplung, final S state, // NOPMD by Dave on
37: // 26.06.23, 22:57
38: final int maximumComputationTime) {
39: Optional<Move<P, S>> bestMove = Optional.empty();
40: try {
41:
42: final Long startTime = System.currentTimeMillis();
43: final Optional<Collection<Move<P, S>>> possiblesMovesOptional = kopplung.getPossibleMoves(state);
44:
45: if (possiblesMovesOptional.isPresent() && possiblesMovesOptional.get().size() > 0) {
46:
47: for (int i = 0;; i++) {
48: Integer bestMoveScore = Integer.MIN_VALUE;
49:
50: Optional<Move<P, S>> iterationBestMove = Optional.empty();
51: Integer iterationBestMoveScore = Integer.MIN_VALUE;
52:
53: if ((System.currentTimeMillis() - startTime) > (maximumComputationTime / 2)) {
54: break;
55: }
56:
57: for (final Move<P, S> move : possiblesMovesOptional.get()) {
58:
59: final S copiedState = state.deepCopy();
60: final P currentPlayer = kopplung.getCurrentPlayer(copiedState).get();
61: move.applyTo(copiedState, currentPlayer);
62: copiedState.nextTurn();
63:
64: final Integer moveScore = -this.negamax(kopplung, copiedState, i, Integer.MIN_VALUE,
65: Integer.MAX_VALUE);
66:
67: if (moveScore > iterationBestMoveScore) {
68:
69: iterationBestMove = Optional.of(move);
70: iterationBestMoveScore = moveScore;
71: }
72: }
73:
74: if (iterationBestMoveScore > bestMoveScore) {
75: bestMove = iterationBestMove;
76: bestMoveScore = iterationBestMoveScore;
77: }
78: }
79: }
80: return bestMove;
81: } catch (final Exception e) {
82:
83: return bestMove;
84: }
85:
86: }
87:
88: /**
89: * Extracted.
90: *
91: * @param kopplung
92: * @param state
93: * @param move
94: * @return
95: * @throws GameException
96: */
97: private S simulateMove(final IKopplung<P, S> kopplung, final S state, final Move<P, S> move) throws GameException {
98: final S copiedState = state.deepCopy();
99: final P currentPlayer = kopplung.getCurrentPlayer(copiedState).get();
100: move.applyTo(copiedState, currentPlayer);
101: copiedState.nextTurn();
102: return copiedState;
103: }
104:
105: /**
106: * Performs the NegaMax algorithm to evaluate the score of a Game state.
107: * Too complex, but not easily simplifyable. Warning suppressed.
108: *
109: * @param kopplung The game object representing the specific game being played.
110: * @param state The current state of the game.
111: * @param depth The current depth of the algorithm.
112: * @param alpha The alpha value for alpha-beta pruning.
113: * @param beta The beta value for alpha-beta pruning.
114: * @return The evaluated score of the state.
115: * @throws Exception
116: */
117: @SuppressWarnings({ "checkstyle:CyclomaticComplexity", "PMD.CyclomaticComplexity", "PMD.CognitiveComplexity" })
118:
119: private Integer negamax(final IKopplung<P, S> kopplung, final S state, final Integer depth, final Integer alpha,
120: final Integer beta) throws GameException {
121:
122: if (depth == 0 || kopplung.getIsGameOver(state).get()) {
123:
124: return kopplung.evalState(state).get();
125: }
126:
127: final Optional<Collection<Move<P, S>>> possiblesMovesOptional = kopplung.getPossibleMoves(state);
128: if (possiblesMovesOptional.isPresent() && possiblesMovesOptional.get().size() > 0) {
129:
130: Integer score = Integer.MIN_VALUE;
131: Integer modAlpha = alpha;
132: for (final Move<P, S> move : possiblesMovesOptional.get()) {
133:
134: final S copiedState = this.simulateMove(kopplung, state, move);
135:
136: final Integer childScore = -this.negamax(kopplung, copiedState, depth - 1, -beta, -modAlpha);
137: if (childScore > score) {
138:
139: score = childScore - depth;
140: }
141: modAlpha = Math.max(modAlpha, score);
142: if (modAlpha >= beta) {
143:
144: break;
145: }
146:
147: }
148:
149: return score;
150: }
151:
152: throw new GameException("Something went wrong with Negamax");
153:
154: }
155:
156: }